package com.lfg.leetcode.leetcode0;

public class No62uniquePaths {

    public static void main(String[] args) {
        int ret = uniquePaths(7, 3);
        System.out.println(ret);
    }

    public static int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 1;
        }
        int[][] nums = new int[m][n];
        nums[m - 1][n - 1] = 1;
        for (int y = n - 2; y >= 0; y--) {
            nums[m - 1][y] += nums[m - 1][y + 1];
        }
        for (int x = m - 2; x >= 0; x--) {
            nums[x][n - 1] += nums[x + 1][n - 1];
        }
        for (int x = m - 2; x >= 0; x--) {
            for (int y = n - 2; y >= 0; y--) {
                nums[x][y] += nums[x][y + 1] + nums[x + 1][y];
            }
        }
        return nums[0][0];
    }


}

